/**
 * @author ghp
 * @title
 * @description
 */
public class Test {

    private int min = Integer.MAX_VALUE;

    public int numSquares(int n) {
        int sqrt = (int) Math.sqrt(n);
        int[] square = new int[sqrt];
        for (int i = 1; i <= sqrt; i++) {
            square[i - 1] = i * i;
        }
        dfs(square, n, sqrt - 1, 0, 0);
        return min == Integer.MAX_VALUE ? -1 : min;
    }

    private void dfs(int[] square, int target, int index, int count, int sum) {
        if (index < 0 || count >= min) {
            return;
        }
        if (sum == target) {
            min = Math.min(min, count);
            return;
        }
        // 计算剩余最大次数
        int maxCount = (target - sum) / square[index];
        for (int i = maxCount; i >= 0; i--) {
            dfs(square, target, index - 1, count + i, sum + i * square[index]);
        }
    }
}
